package leetcode_day._2022._202208._1120;

import general_class.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 654. 最大二叉树
 * 算法：递归、单调栈
 *
 * @author yzh
 * @version 1.0
 * @date 2022/8/20 19:03
 */
public class _20 {

    public static void main(String[] args) {
        System.out.println(new _20().constructMaximumBinaryTree(new int[]{3, 2, 1, 6, 0, 5}));
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return recursion(0, nums.length - 1, nums);
    }

    TreeNode recursion(int start, int end, int[] nums) {
        if (start > end) return null;
        int idx = getMaxIdx(start, end, nums);
        TreeNode head = new TreeNode(nums[idx]);
        head.left = recursion(start, idx - 1, nums);
        head.right = recursion(idx + 1, end, nums);
        return head;
    }

    int getMaxIdx(int start, int end, int[] nums) {
        int max = Integer.MIN_VALUE, idx = -1;
        for (; start <= end; start++) {
            if (max < nums[start]) {
                max = nums[start];
                idx = start;
            }
        }
        return idx;
    }

    public TreeNode constructMaximumBinaryTreeStack(int[] nums) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        for (int num : nums) {
            TreeNode cur = new TreeNode(num);
            // 找到 [0, i - 1] 的最大元素
            while (!stack.isEmpty() && stack.peek().val < num) cur.left = stack.pop();
            if (!stack.isEmpty()) stack.peek().right = cur;
            stack.push(cur);
        }
        return stack.peekLast();
    }

}
